package cn.algorithms_4ed.algo.prior_queen;

/**
 * 大顶 优先队列
 * <p/>
 * User: erhu
 * Date: 13-6-22
 * Time: 下午10:54
 */
public class MaxPQ<T extends Comparable<T>> {

    private T[] data;
    private int size;

    public MaxPQ(int max_size) {
        data = (T[]) new Comparable[max_size + 1];
    }

    public void insert(T t) {
        // 家族壮大
        if (size + 1 >= data.length) {
            data = enlarge(data, 2);
        }

        data[++size] = t;
        swim(size);
    }

    private T[] enlarge(T[] data, int times) {
        T[] t_pq = (T[]) new Comparable[data.length * times];
        System.arraycopy(data, 0, t_pq, 0, data.length);
        return t_pq;
    }

    public T delMax() {
        T max = data[1];
        exchange(1, size--);
        data[size + 1] = null;
        sink(1);

        // 家族减员
        if (size <= data.length / 4) {
            // 椅子数减半
            T[] t_pq = (T[]) new Comparable[data.length / 2];
            System.arraycopy(data, 0, t_pq, 0, data.length / 4);
            data = t_pq;
        }
        return max;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    private boolean less(int i, int j) {
        return data[i].compareTo(data[j]) < 0;
    }

    private void exchange(int i, int j) {
        T t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    /**
     * 儿子 k 向上游啊游
     *
     * @param k
     */
    private void swim(int k) {
        // (游到根了 || 老子比我大) ==> 游不动的。
        if (k <= 1 || !less(k / 2, k)) {
            return;
        }
        // 儿子变成老子
        exchange(k / 2, k);
        // 继续游
        swim(k / 2);
    }

    /**
     * 下沉
     */
    private void sink(int k) {

        while (2 * k <= size) {
            int big_index = 2 * k;

            // 找大儿子
            if (big_index < size && less(big_index, big_index + 1)) {
                big_index++;
            }

            // 大儿子比老子大，继续下沉
            if (less(k, big_index)) {
                exchange(big_index, k);
                k = big_index;
                continue;
            }

            // 大儿子比老子小，本家关系正确；
            break;
        }
    }

    public void sort() {
        int N = data.length;
        // 建大顶堆
        for (int k = N / 2; k >= 1; k--) {
            sink(k);
        }

        while (N > 1) {
            // 把堆顶元素放到最后面
            exchange(1, N--);
            // 将儿子下沉到正确的位置
            // while 循环意为=》直到所有元素下沉完毕；
            sink(1);
        }
    }
}
